#include <bits/stdc++.h>
using namespace std;

// 模板类：区间加法和区间求和的懒惰线段树
template <typename T>
class SegmentTreeLazyRangeAdd {
private:
    vector<T> tree; // 线段树存储节点值
    vector<T> lazy; // 懒惰标记数组
    vector<T> *data; // 指向初始化数组
    int n; // 数组大小
    int root; // 线段树的根节点索引
    int tree_size; // 线段树数组的大小
    int last_index; // 数组的最后一个索引

    // 维护当前节点的懒惰标记
    void push_down(int left, int right, int node);

    // 区间求和
    T query_range(int query_left, int query_right, int node_left, int node_right, int node);

    // 区间加法
    void update_range(int update_left, int update_right, T value, int node_left, int node_right, int node);
    // 建树
    void build(int start, int end, int node);

public:
    // 构造函数
    explicit SegmentTreeLazyRangeAdd(vector<T> &input_data);

    // 查询区间和
    T query_range(int left, int right);

    // 更新区间加值
    void update_range(int left, int right, T value);

    /*// 显示线段树和懒惰标记 测试用
    void display(int node, int depth = 0) {
        if (node >= tree_size || tree[node] == 0) return;
        display(node * 2, depth + 1);
        for (int i = 0; i < depth; ++i) putchar('\t');
        printf("Node Value: %d, Lazy Value: %d\n", tree[node], lazy[node]);
        display(node * 2 + 1, depth + 1);
    }*/
};
